#ifndef VECTOR_H
#define VECTOR_H
#include <bits/stdc++.h>
using namespace std;

template <class T> class Vector{
#define SPARE 4
private:
	// n is the size of vector, and r is the size of capacity.
	int n,r;
	// Elements
	T* a;
public:
	// Constructor
	explicit Vector(const int & s = 0) : n(s), r(s + SPARE) {
		a = new T[s];
	}
	// "Big-Five"
	// Copy Constructor
	Vector(const Vector & p): n(p.n), r(p.r), a(nullptr) {
		a = new T[r];
		for(int i = 0; i < n; ++i) a[i] = p.a[i];
	}
	// Move Constructor
	Vector(Vector && p): n(p.n), r(p.r), a(p.a) {
		p.n = 0, p.r = 0, p.a = nullptr;
	}
	// Operator = (Copy)
	Vector & operator = (const Vector & p) {
		Vector cp = p;
		swap(*this, cp);
		return *this;
	}
	// Operator = (Move)
	Vector & operator = (Vector && p) {
		swap(n, p.n), swap(r, p.r), swap(a, p.a);
		return *this;
	}
	// Destructor
	~Vector() {delete[] a;}
	
	// Resize the size to s (generally, s > n). If the capacity is full, then double the size of capacity.
	inline void resize(const int & s) {
		if(s > r) reserve(s << 1);
		n = s;
	}
	// Reserve the size of capacity to s. (generally, s > r)
	inline void reserve(const int & s) {
		if(s < n) return;
		T* tmp = new T[s];
		for(int i = 0; i < n; ++i) tmp[i] = a[i];
		r = s;
		swap(a, tmp);
		delete[] tmp;
	}
	
	// Operator []
	inline const T operator [] (const int& i) const {
		if(i < 0 || i >= n) exit(3221225477);
		return a[i];
	}
	inline T & operator [] (const int& i) {
		if(i < 0 || i >= n) exit(3221225477);
		return a[i];
	}
	
	// Basic routines
	// Judge if the vector is empty.
	inline const bool empty() const {
		return !n;
	}
	// Return the size of the vector.
	inline const int size() const {
		return n;
	}
	// Return the size of the capacity.
	inline const int capacity() const {
		return r;
	}
	
	// Return the last element of the vector.
	inline int back(){
		if(!n) exit(3221225477);
		return a[n-1];
	}
	// Push x to the back of the vector. If the vector is full, then double the size of capacity.
	inline void push_back(const T & x) {
		if(n == r) reserve(r << 1);
		a[n++] = x;
	}
    inline void push_back(T && x){
        if(n == r) reserve(r << 1);
        a[n++] = x;
    }
	// Pop the last element of the vector
	inline void pop_back() {
		if(!n) exit(3221225477);
		--n;
	}
	// Insert x between the (i-1)th and ith elements. assert 0 <= i <= n.
	inline void insert(const T & x, int i) {
		if(i < 0 || i > n) exit(3221225477);
		if(n == r) reserve(r << 1);
		for(int j = n-1; j >= i; --j) a[j+1] = a[j];
		++n, a[i] = x;
	}
	
	// Iterators
	typedef T* iterator;
	
	// Return the first address of the vector.
	inline iterator begin() {
		return &a[0];
	}
	inline const iterator begin() const {
		return &a[0];
	}
	// Return the last address of the vector.
	inline iterator end() {
		return &a[n];
	}
	inline const iterator end() const {
		return &a[n];
	}
	// Find the address of x. If x doesn't exist, return the end iterator.
	inline iterator find(const T& x) {
		for(int i = 0; i < n; ++i)
			if(a[i] == x) return &a[i];
		return &a[n];
	}
};
#endif